package com.tongji.diy.model.furniturePlacementOptimization
{
	import com.tongji.diy.event.furnitureOptimizationEvent.IterationPerFrameStartEvent;
	import com.tongji.diy.event.furnitureOptimizationEvent.OptimizationShowCurrentLayoutEvent;
	import com.tongji.diy.model.RoomDataModel;
	import com.tongji.diy.model.RoomDataVO;
	import com.tongji.diy.model.furniturePlacementOptimization.accessibleBoundingBoxes.FurnitureAcessibleBoundingBoxA;
	import com.tongji.diy.model.furniturePlacementOptimization.accessibleBoundingBoxes.FurnitureBasicBoundingBox;
	import com.tongji.diy.model.furniturePlacementOptimization.complementStructs.TempFurnitureInfor;
	import com.tongji.diy.utils.OptimizationMath;
	import com.tongji.diy.utils.PolygonMath;
	
	import de.polygonal.ds.DListNode;
	
	import flash.geom.Point;
	import flash.geom.Vector3D;
	
	import org.robotlegs.mvcs.Actor;
	
	[Bindable]
	public class FurnitureOptimizationModel extends Actor
	{
		[Inject]
		public var roomModel:RoomDataModel;
		//private var optBasicBoundBoxes:Vector.<FurnitureBasicBoundingBox> = new Vector.<FurnitureBasicBoundingBox>;
		private var optAccessibleBoundBoxes:Vector.<FurnitureBasicBoundingBox> = new Vector.<FurnitureBasicBoundingBox>;
		
		private var orientedSelectionList:Vector.<Number> = new Vector.<Number>;
		
		//test
		private var testT:Number = OptimizationParameter.startedTemperature;
		private var testTCount:int = 0;
		private var testTempCost:Number = 0;
		private var testShowCount:Number=0;
		private var testRefresh:int = 50;
		private var angleCost:Number = 0;
		private var distanceCost:Number = 0;
		
		//room data
		private var roomCircumference:Number = 0;//房间周长
		private var roomSideLengthList:Vector.<Number> = new Vector.<Number>;//边长数组，该数组存储的是从起始点开始到包括该条边为止的之前所有边的长度和
		private var roomWallVerticalOrentationList:Vector.<Point> = new Vector.<Point>;//该数组所存储的是垂直于房间每条边且指向房间内部的向量
		private var roomPoints:Vector.<Point> = new Vector.<Point>;
		
		public function FurnitureOptimizationModel()
		{
			super();
		}
		
		public function addBasicBoundingBox(location:Vector3D,width:Number,length:Number,height:Number, angle:Number,parentRoomIndex:int, pairFurnitureIndex:Number,furnitureClass:int):void
		{
			
			////////////////////////////////
			//这个函数准备弃用
			
			
			
			
			//已经添加过的家具修改location等值，未添加的家具进行添加
			/*var addSign:Boolean = true;
			for(var i:uint = 0;i < optAccessibleBoundBoxes.length; i++)
			{
				if(optAccessibleBoundBoxes[i].pairFurnitureIndex == pairFurnitureIndex)
				{
					addSign = false;
					optAccessibleBoundBoxes[i].location = location;
					optAccessibleBoundBoxes[i].angle = angle;
					optAccessibleBoundBoxes[i].parentRoomIndex = parentRoomIndex;
					optAccessibleBoundBoxes[i].furnitureClass = furnitureClass;
					break;
				}
			}
			
			if(addSign)
			{
				switch(furnitureClass)
				{
					case OptimizationParameter.DESK:
					case OptimizationParameter.CHAIR:
					case OptimizationParameter.SIDE_TABLE:
					case OptimizationParameter.TV:
					case OptimizationParameter.OTHER:
						
						var newAccessibleBoxA:FurnitureAcessibleBoundingBoxA = new FurnitureAcessibleBoundingBoxA(location,width,length,height,angle,parentRoomIndex, pairFurnitureIndex,furnitureClass);
						optAccessibleBoundBoxes.push(newAccessibleBoxA);
						break;
					
					case OptimizationParameter.CABINET:	
					case OptimizationParameter.WASH_BLOW:
					case OptimizationParameter.MULITI_SOFA:
					case OptimizationParameter.SINGLE_SOFA:
					case OptimizationParameter.HOLISTIC_KITCHEN:
					case OptimizationParameter.BEDSTAND:
					case OptimizationParameter.FIREPLACE:
						
						var newAccessibleBoxB:FurnitureAcessibleBoundingBoxB = new FurnitureAcessibleBoundingBoxB(location,width,length,height,angle,parentRoomIndex, pairFurnitureIndex,furnitureClass);
						optAccessibleBoundBoxes.push(newAccessibleBoxB);
						break;
					
					case OptimizationParameter.BED:
					case OptimizationParameter.CLOESTTOOL:
						
						var newAccessibleBoxC:FurnitureAcessibleBoundingBoxC = new FurnitureAcessibleBoundingBoxC(location,width,length,height,angle,parentRoomIndex, pairFurnitureIndex,furnitureClass);
						optAccessibleBoundBoxes.push(newAccessibleBoxC);
						break;
				}
			}*/
		}
		
		public function startOptimization():void
		{
			analysis();
			simulatedAnnealingProcess();
		}
		
		private function analysis():void
		{
			analysisRoom();
			analysisSpaceOrdinal();			
		}
		
//		private function analysisRoom():void
//		{
//			var room:RoomDataVO = roomModel.rooms[optAccessibleBoundBoxes[0].parentRoomIndex];
//			var node:DListNode = room.roomPointList.head;
//			while(1)
//			{
//				var a:Number = node.next.data.globalX - node.data.globalX;
//				var b:Number = node.next.data.globalY - node.data.globalY;
//				roomSideLengthList.push(Math.sqrt(a*a + b*b));
//				var c:Number = node.next.next.data.globalX - node.next.data.globalX;
//				var d:Number = node.next.next.data.globalY - node.next.data.globalY;
//				//通过叉积的方法找出指向房间内部且垂直于墙的方向向量
//				if((a*a + b*b) * (a*d - c*b) > 0)
//					roomWallVerticalOrentationList.push(new Point(-b,a));
//				else
//					roomWallVerticalOrentationList.push(new Point(b,-a));
//				node = node.next;
//				if(node == room.roomPointList.head)
//					break;
//			}
//		}
//		
		//给出家具的可选角度，放入列表orientedSelectionList中。可选角度的选取是根据房间墙的方向做的选择。
		private function analysisRoom():void
		{
			var tempRoom:RoomDataVO = roomModel.rooms[optAccessibleBoundBoxes[0].parentRoomIndex];
			var node:DListNode = tempRoom.roomPointList.head;
			while(1)
			{
				var orientedDriection:Point = new Point(node.next.data.globalX - node.data.globalX, node.next.data.globalY - node.data.globalY);
				if(orientedDriection.x * -1 < 0)
				{
					orientedSelectionList.push(Math.PI/2 - PolygonMath.vectorAngle(orientedDriection, new Point(0,-1)));
				}
				else
				{	
					orientedSelectionList.push(Math.PI/2 + PolygonMath.vectorAngle(orientedDriection, new Point(0,-1)));
				}
				
				//trace("angle",orientedSelectionList[orientedSelectionList.length-1])
				var a:Number = node.next.data.globalX - node.data.globalX;
				var b:Number = node.next.data.globalY - node.data.globalY;
				roomSideLengthList.push(roomCircumference + Math.sqrt(a*a + b*b));
				roomCircumference = roomSideLengthList[roomSideLengthList.length-1];
				
				//通过叉积的方法找出指向房间内部且垂直于墙的方向向量
				var c:Number = node.next.next.data.globalX - node.next.data.globalX;
				var d:Number = node.next.next.data.globalY - node.next.data.globalY;
				
				if((a*a + b*b) * (a*d - c*b) > 0)
				{
					roomWallVerticalOrentationList.push(new Point(-b/Math.sqrt(a*a+b*b),a/Math.sqrt(a*a+b*b)));
				}
				else
				{
					roomWallVerticalOrentationList.push(new Point(b/Math.sqrt(a*a+b*b),-a/Math.sqrt(a*a+b*b)));
				}
				
				roomPoints.push(new Point(node.data.globalX, node.data.globalY));
				
				node = node.next;
				
				if(tempRoom.roomPointList.head == node)					
					break;
			}
		}
		//给出了家具的大小优先顺序，面积大的家具的spaceOrdinal比小的大，从小到大依次是1,2,3...
		private function analysisSpaceOrdinal():void
		{
			for(var i:int = 0; i < optAccessibleBoundBoxes.length; i++)
			{
				for(var j:int = i+1; j < optAccessibleBoundBoxes.length; j++)
				{
					if(optAccessibleBoundBoxes[i].width * optAccessibleBoundBoxes[i].length > optAccessibleBoundBoxes[j].width * optAccessibleBoundBoxes[j].length)
					{
						var temp:FurnitureBasicBoundingBox = optAccessibleBoundBoxes[i];
						optAccessibleBoundBoxes[i] = optAccessibleBoundBoxes[j];
						optAccessibleBoundBoxes[j] = temp;
					}
				}
			}
			var count:int = 1;
			for(i = 0; i < optAccessibleBoundBoxes.length; i++)
			{
				optAccessibleBoundBoxes[i].spaceOrdinal = count;
				if(i+1 < optAccessibleBoundBoxes.length && optAccessibleBoundBoxes[i+1].width*optAccessibleBoundBoxes[i+1].length > optAccessibleBoundBoxes[i].width*optAccessibleBoundBoxes[i].length)
					count++;
			}
		}
		
		private function simulatedAnnealingStopConditionCaculate(opListLength:int):Number
		{
			var condition:Number = 0;
			for(var i:int = 0; i < opListLength; i++)
			{
				var temp:Number = 1;
				for(var j:int = 0; j < i; j++)
					temp *= 0.8;
				condition += OptimizationParameter.simulatedAnnealingStopCondition * temp;
			}
			return condition;
		}
		
		private function simulatedAnnealingProcess():void
		{	
			//test
			var countS:int = 0;
			
			var T:Number = 100;//OptimizationParameter.simulatedAnnealingStartedTemperature;
			var furnitureList:Vector.<TempFurnitureInfor> = new Vector.<TempFurnitureInfor>;
			for(var i:int = 0; i < optAccessibleBoundBoxes.length; i++)
			{
				toNearestWallDistanceAndAngle(optAccessibleBoundBoxes[i]);
				furnitureList.push(new TempFurnitureInfor(optAccessibleBoundBoxes[i].location, optAccessibleBoundBoxes[i].angle, optAccessibleBoundBoxes[i].angleWithNearestWall));
			}
			
			
			var cost:Number = caculateCostFunction();
			var costNext:Number = Infinity;
			var tempCost:Number = Infinity;
			var count:int = 0;
			var tempT:Number = T;
			var tempFurnitureList:Vector.<TempFurnitureInfor>;
		
			while(Math.abs(costNext - cost) > OptimizationParameter.simulatedAnnealingStopCondition)
			{
				/*trace("endCondition",simulatedAnnealingStopConditionCaculate(optAccessibleBoundBoxes.length))
				trace("cost*",cost)*/
				//if(showLayOutCount % 20 != 0)
				{
					count ++;
					var locationCoefficient:Number = locationCoefficientCaculate(tempT);
					var angleCoefficient:Number = angleCoefficientCaculate(tempT);
					for(i = 0; i < tempT; i++)
					{
						
						tempFurnitureList = searchLayout(locationCoefficient,angleCoefficient);
						countS++;
						//showLayOutCount++;
						tempCost = caculateCostFunction();
						
						if(tempCost < cost)
						{
							costNext = cost;
							cost = tempCost;
							furnitureList = tempFurnitureList;
						}
						else
						{
							var p:Number = Math.exp(-(tempCost - cost/T));
							if(Math.random() < p)
							{
								costNext = cost;
								cost = tempCost;
								furnitureList = tempFurnitureList;
							}
						}
					}
				}

				for(i = 0; i < optAccessibleBoundBoxes.length; i++)
				{
					optAccessibleBoundBoxes[i].angle = furnitureList[i].angle;
					optAccessibleBoundBoxes[i].location = furnitureList[i].location;
				}
				showCurrentLayout();
				tempT = T/(1 + count);
			}
			
			for(i = 0; i < optAccessibleBoundBoxes.length; i++)
			{
				optAccessibleBoundBoxes[i].angle = furnitureList[i].angle;
				optAccessibleBoundBoxes[i].location = furnitureList[i].location;
			}	
			showCurrentLayout();
		}

		public function fragmentsShowAnnealingProcess():void
		{
			analysis();
			iterationProcessPerFrame();
		}
		
		public function iterationProcessPerFrame():void
		{
			testTempCost = testSimulatedAnnealing(testT,testTempCost);
			showCurrentLayout();
			dispatch(new IterationPerFrameStartEvent(IterationPerFrameStartEvent.START_ITERATION));	
		}
		
		private function testSimulatedAnnealing(T:Number, cost:Number):Number
		{
			
			//angle,distance adjust
			var tempAngleCost:Number = 0;
			var tempDistanceCost:Number = 0;
			
			var tempFurnitureList:Vector.<TempFurnitureInfor>;
			var locationCoefficient:Number = locationCoefficientCaculate(T);
			var angleCoefficient:Number = angleCoefficientCaculate(T);
			
			var furnitureList:Vector.<TempFurnitureInfor> = new Vector.<TempFurnitureInfor>;
			
			for(var i:int = 0; i < optAccessibleBoundBoxes.length; i++)
			{
				toNearestWallDistanceAndAngle(optAccessibleBoundBoxes[i]);
				furnitureList.push(new TempFurnitureInfor(optAccessibleBoundBoxes[i].location, optAccessibleBoundBoxes[i].angle, optAccessibleBoundBoxes[i].angleWithNearestWall));
			}
			if(testTCount == 0 && testShowCount == 0)
			{
				cost = caculateCostFunction();
			}
			var costNext:Number = Infinity;//目前未使用，待将来可已通过相邻的两个代价函数之间的差值较小作为迭代的结束条件
			var tempCost:Number = cost;
			
			for(i = testShowCount*testRefresh; i < T && i < (testShowCount+1)*testRefresh; i++)
			{
				tempFurnitureList = searchLayout(locationCoefficient,angleCoefficient);
				tempCost = caculateCostFunction();
				
				if(tempCost < cost)
				{
					costNext = cost;
					cost = tempCost;
					furnitureList = tempFurnitureList;
					tempAngleCost = angleCost;
					tempDistanceCost = distanceCost;
				}
				else
				{
					//与标准模拟退火算法相比替换了函数，该函数是选用y = 1/e^x这个函数，
					//选取目的是f(0)=1,f(infinite)=0,f(x)在0到正无穷积分为1；
					var p:Number = 1/Math.exp(-(cost - tempCost));
					if(Math.random() < p)
					{
						//trace("cost",cost,"tempCost",tempCost)
						costNext = cost;
						cost = tempCost;
						furnitureList = tempFurnitureList;
						tempAngleCost = angleCost;
						tempDistanceCost = distanceCost;
						//trace("$$$$",r, p)
					}
				}
				//trace("cost",cost,"T",T, "tempdistance",tempDistanceCost, "tempangle", tempAngleCost);
			}
			if(i < T)
				testShowCount++;
			else
			{
				testShowCount = 0;
				testTCount++;
				testT = testT/(1 + testTCount);
			}
			
			
			for(i = 0; i < optAccessibleBoundBoxes.length; i++)
			{
				optAccessibleBoundBoxes[i].angle = furnitureList[i].angle;
				optAccessibleBoundBoxes[i].location = furnitureList[i].location;
//				trace("angle",optAccessibleBoundBoxes[i].angle/Math.PI*180,"class",optAccessibleBoundBoxes[i].furnitureClass);
//				trace("angleWithNearestWall",furnitureList[i].testNearAngle, optAccessibleBoundBoxes[i].furnitureClass, optAccessibleBoundBoxes[i].spaceOrdinal)
			}	
			//showCurrentLayout();
//			trace("代价",cost);
//			trace("迭代次数",countS);
			return cost;
		}
		
		private function caculateCostFunction():Number
		{
			var count:Number = 0;
			var accessibleCount:Number = 0;
			angleCost = 0;
			distanceCost = 0;
			for(var i:int = 0; i < optAccessibleBoundBoxes.length; i++)
			{
				/*for(var j:int = i+1; j < optAccessibleBoundBoxes.length; j++)
				{
					for(var k:int = 0; k < optAccessibleBoundBoxes[i].accessibleBoxCenters.length; k++)
					{
						var temp:Point = new Point(optAccessibleBoundBoxes[i].location.x, optAccessibleBoundBoxes[i].location.y).subtract(optAccessibleBoundBoxes[j].accessibleBoxCenters[k]);
						count += OptimizationParameter.accessibleCoefficient * Math.max(0,1 - temp.length/(optAccessibleBoundBoxes[i].diagonal + optAccessibleBoundBoxes[j].accessDiagonals[k]));
						accessibleCount += OptimizationParameter.accessibleCoefficient * Math.max(0,1 - temp.length/(optAccessibleBoundBoxes[i].diagonal + optAccessibleBoundBoxes[j].accessDiagonals[k]));
					}
				}*/
				if(optAccessibleBoundBoxes is FurnitureAcessibleBoundingBoxA)
				{
					count += OptimizationParameter.nearestWallAngleCoefficient * optAccessibleBoundBoxes[i].spaceOrdinal*Math.abs(optAccessibleBoundBoxes[i].angleWithNearestWall)
						+ OptimizationParameter.nearestWallDistanceCoefficient * optAccessibleBoundBoxes[i].spaceOrdinal * optAccessibleBoundBoxes[i].distanceToNearestWall;
				}
					 

				//test, the following para design for test
				angleCost += OptimizationParameter.nearestWallAngleCoefficient * optAccessibleBoundBoxes[i].spaceOrdinal*Math.abs(optAccessibleBoundBoxes[i].angleWithNearestWall);
				distanceCost += OptimizationParameter.nearestWallDistanceCoefficient * optAccessibleBoundBoxes[i].spaceOrdinal * optAccessibleBoundBoxes[i].distanceToNearestWall;
//				trace(optAccessibleBoundBoxes[i].furnitureClass,i,optAccessibleBoundBoxes[i].angleWithNearestWall, optAccessibleBoundBoxes[i].distanceToNearestWall, )
			}
			
				
			//trace("anglecount",anglecount, "distanceCount", distanceCount, "accessibleCount",accessibleCount);
			return count;
		}
		
		private function locationCoefficientCaculate(currentT:Number):Number
		{
			return 500/Math.exp(OptimizationParameter.startedTemperature - currentT)///OptimizationParameter.startedTemperature;
		}
		
		private function angleCoefficientCaculate(currentT:Number):Number
		{
			return currentT/OptimizationParameter.simulatedAnnealingStartedTemperature*1.5;
		}
		
		//找出合法的状态存储在optAccessibleBoundBoxes中
		private function searchLayout(locationCoefficient:Number, angleCoefficient:Number):Vector.<TempFurnitureInfor>
		{
			//var locationRandomList:Vector.<Number> = new Vector.<Number>;
			var tempAngleList:Vector.<Number> = new Vector.<Number>;
			var tempFurnitureList:Vector.<TempFurnitureInfor> = new Vector.<TempFurnitureInfor>;
			var swapSuccessSignal:Boolean = false;
			var searchSccess:Boolean = false;
			
			while(!swapSuccessSignal && !searchSccess)
			{
				if(Math.random() > OptimizationParameter.swapFurnitureProbability)
				{					
					for(var i:int = 0; i < optAccessibleBoundBoxes.length; i++)
					{
//						optAccessibleBoundBoxes[i].location = optAccessibleBoundBoxes[i].location.add(new Vector3D(locationNormalRandomList[i]*locationCoefficient,locationNormalRandomList[i+optAccessibleBoundBoxes.length]*locationCoefficient,0));
//						optAccessibleBoundBoxes[i].angle = orientedSelectionList[Math.floor(Math.random()*orientedSelectionList.length)];
				
						if(!(optAccessibleBoundBoxes[i] is FurnitureAcessibleBoundingBoxA))
						{
							//locationRandomList.push(Math.random());
							searchForLocation(optAccessibleBoundBoxes[i],Math.random());
							while(!furnitureInRoom(optAccessibleBoundBoxes[i]) || basicBoxCollisionTestWithAccessBox(optAccessibleBoundBoxes[i]))
							{
								searchForLocation(optAccessibleBoundBoxes[i],Math.random());
							}
						}
						else
						{
							var tempLocation:Vector3D = optAccessibleBoundBoxes[i].location.clone();
							var tempAngle:Number = optAccessibleBoundBoxes[i].angle;
							optAccessibleBoundBoxes[i].location = optAccessibleBoundBoxes[i].location.add(new Vector3D(OptimizationMath.normalRandom()*locationCoefficient,OptimizationMath.normalRandom()*locationCoefficient,0));
							optAccessibleBoundBoxes[i].angle = orientedSelectionList[Math.floor(Math.random()*orientedSelectionList.length)];
						
							while(!furnitureInRoom(optAccessibleBoundBoxes[i]) || basicBoxCollisionTestWithAccessBox(optAccessibleBoundBoxes[i]))
							{
								optAccessibleBoundBoxes[i].location = tempLocation;
								optAccessibleBoundBoxes[i].angle = tempAngle;
								
								optAccessibleBoundBoxes[i].location = optAccessibleBoundBoxes[i].location.add(new Vector3D(OptimizationMath.normalRandom()*locationCoefficient,OptimizationMath.normalRandom()*locationCoefficient,0));
								optAccessibleBoundBoxes[i].angle = orientedSelectionList[Math.floor(Math.random()*orientedSelectionList.length)];
							}
						}
						toNearestWallDistanceAndAngle(optAccessibleBoundBoxes[i]);
						tempFurnitureList.push(new TempFurnitureInfor(optAccessibleBoundBoxes[i].location, optAccessibleBoundBoxes[i].angle, optAccessibleBoundBoxes[i].angleWithNearestWall));
					}
					
					searchSccess = true;
					
				}
				else
				{
					var randomPositions:Vector.<Number> = new Vector.<Number>;
					randomPositions.push(Math.floor(optAccessibleBoundBoxes.length*Math.random()));
					var position2:Number = randomPositions[0];
					randomPositions.push(position2);
					
					while(randomPositions[0]==randomPositions[1])
						randomPositions[1] = Math.floor(optAccessibleBoundBoxes.length*Math.random());

					if(swapFurnitureLocation(optAccessibleBoundBoxes[randomPositions[0]], optAccessibleBoundBoxes[randomPositions[1]]))
					{
						swapSuccessSignal = true;
						toNearestWallDistanceAndAngle(optAccessibleBoundBoxes[randomPositions[0]]);
						toNearestWallDistanceAndAngle(optAccessibleBoundBoxes[randomPositions[1]]);
						for(i = 0;i < optAccessibleBoundBoxes.length;i++)
						{
							if(i != randomPositions[0] && i != randomPositions[1])
							{
								tempFurnitureList.push(new TempFurnitureInfor(optAccessibleBoundBoxes[i].location, optAccessibleBoundBoxes[i].angle, optAccessibleBoundBoxes[i].angleWithNearestWall));
							}
							else if(i == randomPositions[0])
							{
								tempFurnitureList.push(new TempFurnitureInfor(optAccessibleBoundBoxes[randomPositions[0]].location, optAccessibleBoundBoxes[randomPositions[0]].angle, optAccessibleBoundBoxes[randomPositions[0]].angleWithNearestWall));
							}
							else 
							{
								tempFurnitureList.push(new TempFurnitureInfor(optAccessibleBoundBoxes[randomPositions[1]].location, optAccessibleBoundBoxes[randomPositions[1]].angle, optAccessibleBoundBoxes[randomPositions[1]].angleWithNearestWall));
							}
						}
					}
				}
			}		
			return tempFurnitureList;
		}
		
		private function searchForLocation(furnitureBox:FurnitureBasicBoundingBox, random:Number):void
		{
			var room:RoomDataVO= roomModel.rooms[furnitureBox.parentRoomIndex];
			var length:Number = random * roomCircumference;
			var start:int = Math.floor(length/roomCircumference);
			var location:int;
			if(roomSideLengthList[start] < length)
				location = binarySearch(start+1, roomSideLengthList.length-1,length);
			else if(roomSideLengthList[start] > length)
				location = binarySearch(0, start,length);
			else
				location = start;
		
			//trace("location",location);
			var tempV:Point = roomPoints[(location+1)%roomPoints.length].subtract(roomPoints[location]);
			var furnitureLocation:Vector3D = new Vector3D;
			var position:Number;
			if(location != 0)
			{
				var temp:Number = roomSideLengthList[location] - roomSideLengthList[location-1];
				position = (length - roomSideLengthList[location-1]) / temp * (temp - furnitureBox.width) + furnitureBox.width/2;
			}
			else
			{
				position = length / roomSideLengthList[0] * (roomSideLengthList[0] - furnitureBox.width) + furnitureBox.width/2;
			}
			
			furnitureLocation.x = position*tempV.x/tempV.length + roomPoints[location].x + (furnitureBox.length/2+1) * roomWallVerticalOrentationList[location].x - room.x;
			furnitureLocation.y = position*tempV.y/tempV.length + roomPoints[location].y + (furnitureBox.length/2+1) * roomWallVerticalOrentationList[location].y - room.y;

			
			furnitureBox.location = furnitureLocation;
			furnitureBox.angle = orientedSelectionList[location];
			//test for debug
//			var node:DListNode = room.roomPointList.head;
//			while(1)
//			{
//				trace("room",node.data.globalX,node.data.globalY);
//				node = node.next;
//				if(node == room.roomPointList.head)
//					break;
//			}
//			
//			trace("angle", furnitureBox.angle,"location" ,furnitureBox.location,"width",furnitureBox.width, "length", furnitureBox.length, "class",furnitureBox.furnitureClass);
//			for(var k:int = 0; k < furnitureBox.accessibleBoundingBox.length;k++)
//				trace("boundingbox",furnitureBox.accessibleBoundingBox[k].x + room.x, furnitureBox.accessibleBoundingBox[k].y + room.y);	
		}
		
		private function binarySearch(rangeA:int, rangeB:int, length:Number):int
		{
			if(rangeA == rangeB)
				return rangeA;	
			var L:int = Math.floor((rangeA + rangeB)/2);
			if(roomSideLengthList[L] < length)
				return binarySearch(L+1,rangeB,length);
			else if(roomSideLengthList[L] > length)
				return binarySearch(rangeA,L,length);
			else 
				return L;	
		}
		
		//如果待交换的两个box都是FurnitureAcessibleBoundingBoxA类型则调用swapFurnitureLocation4BoxClassA；若其中有一个FurnitureAcessibleBoundingBoxA类型，另一个不是则交换失败；否则
		//调用swapFurnitureLocation4BoxClassBC处理；
		private function swapFurnitureLocation(boxA:FurnitureBasicBoundingBox, boxB:FurnitureBasicBoundingBox):Boolean
		{
			if((boxA is FurnitureAcessibleBoundingBoxA) && (boxB is FurnitureAcessibleBoundingBoxA))
				return swapFurnitureLocation4BoxClassA(boxA,boxB);
			else if((boxA is FurnitureAcessibleBoundingBoxA) || (boxB is FurnitureAcessibleBoundingBoxA))
				return false;
			else
				return swapFurnitureLocation4BoxClassBC(boxA,boxB);
		}
		
		//对于两个非FurnitureAcessibleBoundingBoxA类型的包围盒进行处理，判断交换是否可以执行，若可执行则进行交换，否则返回false
		private function swapFurnitureLocation4BoxClassBC(boxA:FurnitureBasicBoundingBox, boxB:FurnitureBasicBoundingBox):Boolean
		{
			var locationA:Point = boxB.accessibleBoundingBox[0].add(boxB.accessibleBoundingBox[1]);
			locationA.x /= 2;
			locationA.y /= 2;
			var vector:Point = boxB.accessibleBoundingBox[2].subtract(boxB.accessibleBoundingBox[1]);
			locationA.x += boxA.length / 2 * vector.x / vector.length;
			locationA.y += boxA.length / 2 * vector.y / vector.length;
			
			var locationB:Point = boxA.accessibleBoundingBox[0].add(boxA.accessibleBoundingBox[1]);
			locationB.x /= 2;
			locationB.y /= 2;
			vector = boxA.accessibleBoundingBox[2].subtract(boxA.accessibleBoundingBox[1]);
			locationB.x += boxB.length / 2 * vector.x / vector.length;
			locationB.y += boxB.length / 2 * vector.y / vector.length;
			
			var tempBoxB:FurnitureBasicBoundingBox = boxB.clone();
			var tempBoxA:FurnitureBasicBoundingBox = boxA.clone();
			boxB.location = new Vector3D(locationB.x, locationB.y,0);
			boxB.angle = boxA.angle;
			boxA.location = new Vector3D(locationA.x, locationA.y,0);
			boxA.angle = tempBoxB.angle;
			if(!furnitureInRoom(boxA) || basicBoxCollisionTestWithAccessBox(boxA)
				||!furnitureInRoom(boxB) || basicBoxCollisionTestWithAccessBox(boxB))
			{
				boxA = tempBoxA;
				boxB = tempBoxB;
				return false;
			}
			return true;
		}
		
		//对于两个FurnitureAcessibleBoundingBoxA类型的box进行处理，如果交换后没有家具位于房间外部或者家具间有相互交叉的情况出现返回true
		private function swapFurnitureLocation4BoxClassA(boxA:FurnitureBasicBoundingBox, boxB:FurnitureBasicBoundingBox):Boolean
		{		
			var temp:FurnitureBasicBoundingBox = boxA.clone();
			
			boxA.location = boxB.location;
			boxA.angle = boxB.angle;
			boxB.location = temp.location;
			boxB.angle = temp.angle;			
			
			if(!furnitureInRoom(boxA) || basicBoxCollisionTestWithAccessBox(boxA)
				||!furnitureInRoom(boxB) || basicBoxCollisionTestWithAccessBox(boxB))
			{
				temp = boxA.clone();
				boxA.location = boxB.location;
				boxA.angle = boxB.angle;
				boxB.location = temp.location;
				boxB.angle = temp.angle;
				return false;
			}
			return true;
		}
		
		//基本包围盒相交测试，若相交则返回true
		private function basicBoundingBoxCollisionTest():Boolean
		{
			for(var i:int = 0; i < optAccessibleBoundBoxes.length; i++)
			{
				for(var j:int = i+1; j < optAccessibleBoundBoxes.length; j++)
				{
					if(boundingBoxCollisionTest(optAccessibleBoundBoxes[i].basicBoundingBox2D,optAccessibleBoundBoxes[j].basicBoundingBox2D))
						return true;
				}
			}
			return false;
		}
		
		//所有accessibleBoundBoxes的相交测试,返回值为相交的两盒在accessibleBoundingBoxes的位置
		private function accessibleBoundingBoxCollisionTest():Vector.<int>
		{
			var position:Vector.<int> = new Vector.<int>;
			for(var i:int = 0; i < optAccessibleBoundBoxes.length; i++)
			{
				for(var j:int = i+1; j < optAccessibleBoundBoxes.length; j++)
				{
					if(boundingBoxCollisionTest(optAccessibleBoundBoxes[i].accessibleBoundingBox,optAccessibleBoundBoxes[j].accessibleBoundingBox))
						position.push(i,j);
				}
			}
			return position;
		}
		
		//单一accessibleBoundBox与其他accessibleBoundBox的相交测试,返回值为真，即有包围盒相交；
		private function accessibleBoundingBoxCollisionTestForOne(testAccessibleBox:FurnitureAcessibleBoundingBoxA):Boolean
		{
			for(var i:int = 0; i < optAccessibleBoundBoxes.length; i++)
			{
				if(optAccessibleBoundBoxes[i] != testAccessibleBox && boundingBoxCollisionTest(testAccessibleBox.accessibleBoundingBox,optAccessibleBoundBoxes[i].accessibleBoundingBox))
					return true;
			}
			return false;
		}
		
		//单一basicBoundBox与其他basicBoundBox的相交测试,返回值为真，即有包围盒相交；
		private function basicBoundingBoxCollisionTestForOne2ALL(testAccessibleBox:FurnitureBasicBoundingBox):Boolean
		{
			for(var i:int = 0; i < optAccessibleBoundBoxes.length; i++)
			{
				if(basicBoundingBoxAABB2AABBTest(testAccessibleBox, optAccessibleBoundBoxes[i]))
				{
					if(optAccessibleBoundBoxes[i] != testAccessibleBox && boundingBoxCollisionTest(testAccessibleBox.basicBoundingBox2D,optAccessibleBoundBoxes[i].basicBoundingBox2D))
						return true;
				}
			}
			return false;
		}
		
		//对testBox进行包围盒碰撞测试，测试时testBox的accessible包围盒可以与其他包围盒的accessible包围盒碰撞，但是物体与其他物体包围盒不能碰撞		
		//返回值为true说明两盒子有碰撞，否则没有碰撞
		private function basicBoxCollisionTestWithAccessBox(testBox:FurnitureBasicBoundingBox):Boolean
		{
			for(var i:int = 0;i < optAccessibleBoundBoxes.length; i++)
			{
				if(testBox != optAccessibleBoundBoxes[i] && accessBoxAABBCollisionTest(testBox,optAccessibleBoundBoxes[i]))
				{
					var b1:Boolean = AccessBoxBasicBoxCollisionTest(testBox, optAccessibleBoundBoxes[i]);
					var b2:Boolean = AccessBoxBasicBoxCollisionTest(optAccessibleBoundBoxes[i],testBox);
					if(b1 || b2)
						return true;
				}
			}
			return false;
		}
		
		//两包围盒的accessBox做碰撞测试true
		private function accessBoxAABBCollisionTest(boxA:FurnitureBasicBoundingBox, boxB:FurnitureBasicBoundingBox):Boolean
		{
			if(boxA.accessMaxX < boxB.accessMinX || boxA.accessMinX > boxB.accessMaxX)
				return false;
			if(boxA.accessMaxY < boxB.accessMinY || boxA.accessMinY > boxB.accessMaxY)
				return false;
			return true;
		}
		
		//boxA的accessbox与boxB的basicbox做碰撞测试
		private function AccessBoxBasicBoxCollisionTest(boxA:FurnitureBasicBoundingBox, boxB:FurnitureBasicBoundingBox):Boolean
		{
			if(boxA.accessMaxX < boxB.basicMinX || boxA.accessMinX > boxB.basicMaxX)
				return false;
			if(boxA.accessMaxY < boxB.basicMinY || boxA.accessMinY > boxB.basicMaxY)
				return false;
			if(!boundingBoxCollisionTest(boxA.accessibleBoundingBox,boxB.basicBoundingBox2D))
				return false;
			return true;
		}
		
		//用于两basicboundingBox的AABB包围盒相交测试
		private function basicBoundingBoxAABB2AABBTest(boxA:FurnitureBasicBoundingBox, boxB:FurnitureBasicBoundingBox):Boolean
		{
			if(boxA.basicMaxX < boxB.basicMinX || boxA.basicMinX > boxB.basicMaxX)
				return false;
			if(boxA.basicMaxY < boxB.basicMinY || boxA.basicMinY > boxB.basicMaxY)
				return false;
			return true;
		}
		
		//两个包围盒之间的相交测试，如果返回值为true，说明两盒相交
		private function boundingBoxCollisionTest(boundingBoxA:Vector.<Point>, boundingBoxB:Vector.<Point>):Boolean
		{
			/*
			//用边之间相交测试方法
			for(var i:int = 0; i < boundingBoxA.length; i++)
			{
			var LAPA:Point = boundingBoxA[i];
			var LAPB:Point = boundingBoxA[(i+1)%boundingBoxA.length];
			
			for(var j:int = 0; j < boundingBoxB.length; j++)
			{
			var LBPA:Point = boundingBoxB[j];
			var LBPB:Point = boundingBoxB[(j+1)%boundingBoxB.length];
			
			if(PolygonMath.edgeIntersect(LBPA,LBPB,LAPA,LAPB))	
			{
			return true;
			}
			}
			}*/
			if(PolygonMath.rectangleSeparatingAxisCollisionTest(boundingBoxA,boundingBoxB) != -1)
				return false;
			else
				return true;
		}
		
		//返回值为真，说明家具在房间内部
		private function furnitureInRoom(testFurniture:FurnitureBasicBoundingBox):Boolean
		{
			var tempRoomVector:DListNode = roomModel.rooms[testFurniture.parentRoomIndex].roomPointList.head;
		
//			for(var j:int = 0;j < testFurniture.accessibleBoundingBox.length; j++)
//			{
//				trace("BoundingBox",testFurniture.accessibleBoundingBox[j].add(new Point(roomModel.rooms[testFurniture.parentRoomIndex].x, roomModel.rooms[testFurniture.parentRoomIndex].y)));
//			}
//			var H:DListNode = tempRoomVector
//			while(1)
//			{
//				trace("room", H.data.globalX, H.data.globalY);
//				H = H.next;
//				if(H == tempRoomVector)
//					break;
//			}
			for(var i:int = 0;i < testFurniture.accessibleBoundingBox.length; i++)
			{
				if(!PolygonMath.pointIsInPoly(tempRoomVector, testFurniture.accessibleBoundingBox[i].add(new Point(roomModel.rooms[testFurniture.parentRoomIndex].x, roomModel.rooms[testFurniture.parentRoomIndex].y))))
					return false;
			}
			return true
		}
		
		private function toNearestWallDistanceAndAngle(testFurniture:FurnitureBasicBoundingBox):void
		{
			var H:DListNode = roomModel.rooms[testFurniture.parentRoomIndex].roomPointList.head;
			var tempDistance:Number = Infinity;
			var tempAngle:Number;
			var furnitureLocation:Point = new Point(testFurniture.location.x, testFurniture.location.y).add(new Point(roomModel.rooms[testFurniture.parentRoomIndex].x, roomModel.rooms[testFurniture.parentRoomIndex].y));
			var N:DListNode = H;
			var tempRoomEdgePA:Point;
			var tempRoomEdgePB:Point;
			while(1)
			{
				var distance:Number = PolygonMath.pointToLineSquareDistance(new Point(N.data.globalX, N.data.globalY),new Point(N.next.data.globalX, N.next.data.globalY),furnitureLocation)
				if(distance < tempDistance)
				{
					tempDistance = distance;
					tempRoomEdgePA = new Point(N.data.globalX, N.data.globalY);
					tempRoomEdgePB = new Point(N.next.data.globalX, N.next.data.globalY);
				}
				N = N.next;
				if(N == H)
					break;
			}
			var backVector:Point = testFurniture.basicBoundingBox2D[1].subtract(testFurniture.basicBoundingBox2D[0]);
			var rotateVector:Point = tempRoomEdgePB.subtract(tempRoomEdgePA);
			tempAngle = PolygonMath.vectorAngle(rotateVector, backVector);
			
			testFurniture.angleWithNearestWall = tempAngle; 
			testFurniture.distanceToNearestWall = Math.abs(Math.sqrt(tempDistance) - testFurniture.length/2);
		}
		
		private function showCurrentLayout():void
		{
			dispatch(new OptimizationShowCurrentLayoutEvent(OptimizationShowCurrentLayoutEvent.SHOW_CURRENT_LAYOUT,optAccessibleBoundBoxes));
			/*dispatch(new Event(Scene3D.UPDATE_EVENT));
			dispatch(new Event(Scene3D.RENDER_EVENT));*/
		}	
	}
}